//////////////////////////////////////
// Fast Container Library           //
// MIT License - Copyright (c) 2012 //
//////////////////////////////////////

#pragma once

#include "common.h"


// iterator_category | iterator_type
//
// Note that we define iterator_category here as std::*_iterator_tag
// so that all containers and iterators can be used with stl by including
// the standard header <iterator>. Internally fc will always use iterator_type
// so as not to require any dependencies on external libraries.


//std iterator compatability
namespace std { struct random_access_iterator_tag; }
namespace std { struct bidirectional_iterator_tag; }
namespace std { struct forward_iterator_tag; }
namespace std { struct output_iterator_tag; }
namespace std { struct input_iterator_tag; }


FC_NAMESPACE_BEGIN


//c++ standard iterator types
struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidirectional_iterator_tag {};
struct contiguous_iterator_tag : public random_access_iterator_tag {};


template<class Iterator>
struct iterator_traits
{
	typedef ptrdiff_t		difference_type;
	//typedef typename Iterator::difference_type		difference_type;
	typedef typename Iterator::value_type			value_type;
	typedef typename Iterator::pointer				pointer;
	typedef typename Iterator::reference			reference;
	typedef typename Iterator::iterator_type		iterator_type;
	typedef typename Iterator::iterator_category	iterator_category;
};


template <class T>
struct iterator_traits<T*>
{
	typedef T								value_type;
	typedef T*								pointer;
	typedef T&								reference;
	typedef ptrdiff_t						difference_type;
	typedef contiguous_iterator_tag			iterator_type;
	typedef std::random_access_iterator_tag iterator_category;

};


template <class T>
struct iterator_traits<const T*>
{
	typedef T								value_type;
	typedef const T*						pointer;
	typedef const T&						reference;
	typedef ptrdiff_t						difference_type;
	typedef contiguous_iterator_tag			iterator_type;
	typedef std::random_access_iterator_tag iterator_category;

};


namespace internal
{

	template <class ForwardIterator> inline
		ptrdiff_t distance( ForwardIterator first, ForwardIterator last, forward_iterator_tag )
		{
			ptrdiff_t d(0);
			for( ; first != last; ++first ) ++d;
			return d;
		}

	template <class RandomAccessIterator> inline
		ptrdiff_t distance( RandomAccessIterator first, RandomAccessIterator last, random_access_iterator_tag )
		{
			return last - first;
		}

	template <class ForwardIterator> inline
		void advance( ForwardIterator& it, ptrdiff_t n, input_iterator_tag )
		{
			FC_ASSERT(n > 0);
			while( n-- ) ++it;
		}

	template <class BidirectionalIterator> inline
		void advance( BidirectionalIterator& it, ptrdiff_t n, bidirectional_iterator_tag )
		{
			if( n < 0 ) while( n-- ) --it;
			else while( n-- ) ++it;
		}

	template <class RandomAccessIterator> inline
		void advance( RandomAccessIterator& it, ptrdiff_t n, random_access_iterator_tag )
		{
			it += n;
		}

}


// distance

template <class InputIterator> inline
	ptrdiff_t distance( InputIterator first, InputIterator last )
	{
		return internal::distance( first, last, typename iterator_traits<InputIterator>::iterator_type() );
	}

// advance

template <class InputIterator> inline
	void advance( InputIterator& it, ptrdiff_t n )
	{
		return internal::advance( it, n, typename iterator_traits<InputIterator>::iterator_type() );
	}





FC_NAMESPACE_END
